package algorithm.shipinke;

import java.util.LinkedList;
import java.util.List;

/**
 * 参考 https://juejin.cn/post/6844904153123143687
 * 讲的很不错
 */

public class KMP {

    public static void main(String[] args) {
        String s = "abacaababc";
        String pattern = "ab";

        System.out.println(kmp(s, pattern));

    }


    public static int[] getPrefixTable(String s) {
        if (s == null) throw new NullPointerException();

        int i = 1, j = 0;
        int[] table = new int[s.length()];

        while (i < s.length()) {
            // 当j=0时，比较j和i指向的字符，如果字符不匹配，i对应的前缀表位置填入0，且将i向后移动移位，j原地不变
            if (j == 0 && s.charAt(j) != s.charAt(i)) {
                table[i] = 0;
                i++;
            }

            // 如果j和i指向的字符不匹配，并且此时，j需要回溯到prefix[j-1]的位置，再次与i指向的字符比较，重复此步骤直至j和i指向的字符匹配或者j=0
            else if (j != 0 && s.charAt(j) != s.charAt(i)) {
                j--;
            }

            // 当j和i指向的字符匹配时，i对应的前缀表位置填入(j+1)，且将j和i都后移一位
            else if (s.charAt(j) == s.charAt(i)) {
                table[i] = j+1;
                i++; j++;
            }
        }
        return table;
    }


    /**
     * 将前缀表整体后移一位,第一位用-1补充
     * [0,1,0,1,2] -> [-1,0,1,0,1]
     * @param table 前缀表
     * @return 移动后的前缀表
     */
    public static int[] movePrefixTable(int[] table) {
        for (int i = table.length-1; i >= 0; i--) {
            table[i] = i == 0 ? -1 : table[i-1];
        }
        return table;
    }


    /**
     * 贪婪模式匹配,找出pattern在s中存在的所有开始下标
     * @param s 母串
     * @param pattern 模式串,子串
     * @return 母串中*所有*pattern开始的下标
     */
    public static List<Integer> kmp(String s, String pattern) {
        LinkedList<Integer> beginIndex = new LinkedList<>();

        int[] prefix = movePrefixTable(getPrefixTable(pattern));
        int i = 0, j = 0; // i为母串指针,j为模式串指针

        while (i < s.length()) {

            // 完全匹配的情况
            if (j == pattern.length()-1 && pattern.charAt(j) == s.charAt(i)) {
                beginIndex.add(i - pattern.length() + 1);
                j = prefix[j]; // 继续向后匹配
            }

            // 第i和第j匹配,但是没完,继续向后匹配
            else if (pattern.charAt(j) == s.charAt(i)) {
                i++; j++;
            }

            // 模式串和母串在第i和第j个位置不同
            else {

                // 不是在第一位没找到,根据前缀表移动模式串
                if (j != 0) j = prefix[j];

                // 模式串第一位都没匹配上,模式串和母串各自向右移动一位
                else {
                    i++; j++;
                }
            }
        }
        return beginIndex;
    }

}
